PD ROM 1

home *** CD-ROM | disk | FTP | other *** search

/ PD ROM 1 / PD ROM Volume I - Macintosh Software from BMUG (1988).iso / Graphics / Graphic Demos / Super MandelZoom / Fractals / Super MZ doc part 2 < prev

Wrap

Text File | 1986-12-31 | 25.5 KB | 608 lines | [TEXT/ttxt]

Program Structure ------- --------- As mentioned above, whenever you wait and do nothing the program will finish executing all commands and then automatically draw the image at progressively higher degrees of resolution until it has drawn the whole image at 256x256 resolution. This is accomplished through a complex "multiprocessing" technique which allows commands to be executed in order of importance rather than in the order that they were received. A more detailed explanation of what is going on is given here (also, those trying to understand the source code should find this section particularly useful.) The main control process of Super MANDELZOOM (which is called _EXEC) simulates a batch multitasking system with a pre-emptive "fastest first" priority scheme (with a few exceptions as explained below) At any given time, there may be many activities pending. These activities include evaluating the image, evaluating part of the image selected by the Detail command, redrawing the picture with a new shading table, plotting a Julia curve, running the Query command on a point, etc. Except in two special cases, there is only one process running at a given time. Whenever a command is received or the currently running process finishes normally, control is transfered to _EXEC. _EXEC keeps track of which processes are waiting to start, which ones have been pre-empted ~~~~~~~~~~~~~~~~ ~~~~~~~~~~ (interrupted,) which ones have been aborted (terminated before they finished their job,) and which ones have ~~~~~~~ finished. It then runs that process which is still not finished and which has highest priority. The priority ~~~~~~~~ assignment, from highest to lowest, is as follows ("current selection" is the rectangle most recently selected with the Detail command): Prio # Process Name Activity ------ ------------ ------------------------------------------------------- 0. _EXEC Receiving and interpreting commands 1. _DRAW_PIC Evaluating and/or redrawing the Mandelbrot Set image at 8x8 resolution 2. _JULIA Drawing a picture of a Julia curve 3. _QUERY Determining n_max and attractor period for a point * _D_TRACK Selecting a rectangular section of the image with the mouse * _MOUSE_PT Continuously displaying the coordinates of the point under the cursor 4. _REFILL a. Redrawing the entire image at 1x1 resolution b. Redrawing the entire image at 2x2 resolution c. (etc...) i. Redrawing the entire image at 256x256 resolution 5. _DETAIL Evaluating points in the current selection 6. _IDLE_MODE a. Evaluating points outside the current selection at 16x16 resolution b. Evaluating points outside the current selection at 32x32 resolution c. (etc...) e. Evaluating points outside the current selection at 256x256 resolution 7. _Q_SEARCH Breadth-first search for all points which are adjacent to points of a different count value, at 256x256 resolution _D_TRACK and _MOUSE_PT are special cases - they are run concurrently with _REFILL, _DETAIL, _IDLE_MODE, and/or _Q_SEARCH. See the descriptions of _D_TRACK and _MOUSE_PT below. The following table shows the relationship between commands and processes: __ Process | ~~---__ Name | _EXEC _JULIA _DRAW_PIC _QUERY _D_TRACK _MOUSE_PT _REFILL _DETAIL _IDLE_MODE _Q_SEARCH Command ~~--__ | ----------------+---------------------------------------------------------------------------------------------- (Program Start) | * * * * ----------------+---------------------------------------------------------------------------------------------- Palette | * Julia | * * * • Query | * * Edit Table | * * • Detail | * * * • * • MousePt | * */• Scroll | * * • • * • * • Zoom | * * • • * • * • Set N_max | * * • • * • * • Set # of Bits | * * • • * • * • In this table, an asterisk indicates that the command on the left causes the process to become initiated. A bullet (•) indicates that the command on the left causes the process to be aborted. All processes except _JULIA finish by themselves if they are given enough time. _JULIA The Julia curve program plots the iterates of Z under the inverse of the self-squared function described in n the Mathematical Background section. This function has two possible values, and contains a square root. The choice is made pseudo-randomly, and computations are made using 16-bit accuracy. _JULIA aborts when you press the mouse button -- the next time it runs it does not continue where it left off but starts over from scratch. _DRAW_PIC _DRAW_PIC evaluates and draws the picture at 8x8 resolution. It must be run at least once on an image before _REFILL, _DETAIL, _IDLE_MODE, and _Q_SEARCH can be run because it initializes the array with the correct structure so that those routines can tell what size each of the pixels are. Therefore, it is never pre-empted but runs until it is finished. Because it is sometimes noticably slow, it changes the cursor to a wristwatch while it is running. _QUERY _QUERY runs the iterated function (1b.) above on just one point, using 32-bit math. If condition (4) above is still satisfied after 1000 iterations, _QUERY runs for another 1000 iterations looking for an attractor. It finds an attractor if during these 1000 iterations it finds a value Z which is no more than 5 units away from n Z in either the real or imaginary directions. In this case, the period of the attractor is n - 1000. If it 1000 finds a value Z which does not meet condition (4), then a non-member point has been found and count equals n. n If Z meets condition (4) and no attractor was found the point is reported as having count>2000 and cycle 2000 unknown. _QUERY never takes more than a second or so to run, so it is not pre-empted or aborted by anything. _REFILL _REFILL runs in nine passes. (In this table, the times are based on the benchmark test described above.) Pass Resolution Time (Sec.) ---- ---------- ----------- 1 1x1 0.0 2 2x2 0.0 3 4x4 0.1 4 8x8 0.1 5 16x16 0.3 6 32x32 0.7 7 64x64 2.2 8 128x128 5.8 9 256x256 + 18.3 ------ Total 27.5 In each pass, _REFILL scans the array and draws all areas which have been evaluated at the indicated resolution or more. There are two reasons why pass number 8 (for example) doesn't take 4 times as long as pass number 7. First, although pass number 8 makes more QuickDraw calls, the individual pixels involved are smaller and don't take as long as those in pass 7. Second, in each pass _REFILL skips a point if its area of the screen has already been filled in with the proper shade of gray by one of the previous passes. The 256x256 array used to store the "count" values for the points in the image has 65,536 entries. Each of these is one byte long. The high bit is a flag used by the _DETAIL routine (see below) and the other seven bits store a value from 0 to 127. If this value is zero, the point hasn't been evaluated yet. If the value is 127, the point is in the Mandelbrot Set. All other values indicate what the count for that point is. Since the "count" value can actually be as high as 1000, the "count" must be translated to a "modified count" which falls somewhere in the range 1 to 126. The modified count is used as an index into the shading table, which has 128 entries (and the structure of which is described under the "Edit Shading Table" section under Using the Program ~~~~~ ~~~ ~~~~~~~ above.) _REFILL is pre-empted by _JULIA. All other commands cause it to abort except _DETAIL, which waits until _REFILL is done running. _DETAIL _DETAIL scans through each of the points in the selected rectangle, and determines what resolution it has been computed at. If the point has not yet been computed at 256x256 resolution, _DETAIL splits the point into four points of the next-higher level of resolution, and evaluates and plots each of the smaller points. _DETAIL does not use an adjacency algorithm (described below under _IDLE_MODE) because oftentimes not all of the neighbors of a point being evaluated by _DETAIL have been evaluated to the same leval of resolution. _DETAIL is pre-empted by all processes except _IDLE_MODE and _Q_SEARCH. It is aborted by scrolling, zooming, changing n_max or the number of bits, and by sending another Detail command. On a 512K Mac it does not run at all after _Q_SEARCH has started, because _Q_SEARCH does not "split" pixels in a way which is compatible with the algorithm used in _DETAIL. _IDLE_MODE _IDLE_MODE runs in five passes. (The times are based on the benchmark test described above.) Pass From To Adjacency Alg. Time (Sec.) ---- ------- ------- -------------- ----------- 1 8x8 16x16 no 2.6 2 16x16 32x32 no 5.9 3 32x32 64x64 no 20.9 4 64x64 128x128 yes 49.9 5 128x128 256x256 yes 160.6 ---------- Total 239.9 In each pass, the program scans the entire image looking for pixels which are drawn in the level of resolution listed in the "From" column. When it finds one, it breaks the pixel up into four smaller pixels. When it has done this for the entire image, the picture has the resolution shown in the "To" column. When the adjacency algorithm is enabled (passes 4 and 5) _IDLE_MODE skips a pixel if it has no neighbors with a different value of "count". This means that if there is a large area on the screen which is all the same value of "count", _IDLE_MODE will skip all the pixels in the middle and break up only the ones around the edges. This is a fairly good algorithm, and normally it will perform quite well, giving 10% to 40% speed increases (or sometimes more.) However, it does not always work, because sometimes a region which appears to be solid at low resolution turns out to contain some pixels of a different shade when drawn at high resolution. To see one of these regions, run Super MANDELZOOM and set it to Center=0.00+0.75i, Size=0.25. You can do this by zooming in once, hitting the up arrow three times and then zooming in three times. In the very lower-left of the picture you will see a "cusp" of the gray region. This cusp is an example of a region which looks solid black at low resolution but which actually has some non-black points at high resolution. Now wait until it finishes plotting the "cusp" at 256x256 resolution (but before it starts running _Q_SEARCH, see below.) Then, with the Detail command select the area at the very tip of the cusp, and select a good-sized part of the black space around it, too. You will see the point get a little bit longer: the area at the very end of the cusp was missed by _IDLE_MODE. To avoid this problem, two solutions are used in combination. First, the adjacency algorithm is not used in the first three passes; therefore it never misses any features which are more than 3 pixels across. Second, the process _Q_SEARCH, which runs after _IDLE_MODE is finished, finds and draws any points which were missed by _IDLE_MODE. _IDLE_MODE is pre-empted by all other processes except _Q_SEARCH and the two time-sharing processes. It is aborted by scrolling, zooming, changing n_max and changing the number of bits. _Q_SEARCH _Q_SEARCH is a breadth-first search for all points in the image which are adjacent to a point with a different value of "count". The breadth-first search finds all member points which lie on the border between one solid region and another. The search is possible because all boundary points are connected to each other - that is, there are no "island regions" anywhere (except certain features which are narrower than the resolution used to draw the image.) _Q_SEARCH simply starts in the upper-left corner and "walks" along the edges of the image and along all of the "contours" in the image itself, tracing along each contour from both ends until it meets itself in the middle. _Q_SEARCH is an improvement of the algorithm used in the browser program written in C by John White (jnw@mcnc.UUCP) at the Microelectronics Center of NC; RTP, NC, and posted to the USENET computer network. It was once used as the primary evaluation algorithm of the whole program, because it offers speed savings comparable to those of _IDLE_MODE's adjacency algorithm. It was fun to watch _Q_SEARCH "trace out" the picture, but in the end, _IDLE_MODE proved to be faster. (_Q_SEARCH has a lot more overhead) _Q_SEARCH is pre-empted by every other process. _DETAIL will make _Q_SEARCH start over again if it isn't finished. Low-Level Math Routines For each of the three higher precisions there are optimized LongMult (compute X times Y) and LongSquare (compute X squared) routines. Programmers wishing to speed up their own programs can use these LongMult and LongSquare routines; they serve quite well as "generic" integer multiply routines. (If you don't have the source code, the "About..." menu command in the program tells you how to get it.) For 16-bit math, I have one sign bit, one integer bit and 14 bits for the fraction, and I just use the MULS instruction to get a product with 28 bits to the right of the "binary point", and I shift it into position to get the answer. My 32-bit numbers have one sign bit, one bit to the left of the point and 30 bits to the right of the point. I use a "standard" 32x32 -> 64 integer multiply algorithm, and this gives me a product with one sign bit, 3 bits to the left of the binary point, and 60 bits to the right. I then shift it left 2 bits and the high 32 bits is my answer. For the 30-bit math, my numbers are in the same format as the 32-bit numbers, but I ignore one of the four partial products. In the following diagram, a, b, c, and d are 16-bit pieces of the two factors, and p through w are 16-bit pieces of the partial-products. In my 30-bit math algorithm, I don't compute the partial product b * d. That means that my answer is only correct in the highest 32 bits, so when I shift it to the left I get two zeros in the bottom two bits - thus, I get 30-bit precision out of it (but I save 25% of my time, or 33% for the LongSquare routine.) factor 1 a b times factor 2 x c d ------------ b * d p q a * d r s b * c t u a * c + v w ------------------------ product v r+t+w p+s+u q For 18-bit math, I have one sign bit, 15 bits to the left of the point and 16 to the right. (This is Apple's 32-bit fixed-point format.) As with the 30 and 32-bit routines, both factors are made positive before I multiply them, so that means that a and c are both either 0 or 1. Therefore, a*c equals a AND c, and a*d and b*c are both done by testing a (or c) and adding d (or b) if it's non-zero. That means that I only need one MULU, for b*d. The answer has one sign bit, 31 bits to the left and 32 bits to the right of the binary point, and I just take the two middle words for my answer, no shifting required. Future Considerations The modified-count value 126 is unused because it is reserved for future optimization of the "change n_max" command. Increasing the value of n_max can be made faster if the program re-evaluates only those points which were previously regarded as member points. Decreasing the value of n_max can be made much faster -- here, the program doesn't have to re-evaluate any points, instead it can just draw points as member points if they are greater than the user's specified value of n_max. The complications in implementing these changes result from the user possibly changing n_max several times and scrolling the picture, fast enough so the computer cannot finish the whole image at any value of n_max. In this case, the picture might become permanently inconsistent, containing some areas which have been evaluated to a greater n_max than others. _QUERY can be improved by making its search technique more elaborate. When the iterates of a point with period k converge on the point's attractor, successive values Z , Z , Z , etc. converge on the attractor n n+k n+2k point Z by means of a sort of spiral-shaped pattern. Because of this spiral-shaped pattern, points Z and n+∞k n Z end up being much closer to each other than either is to the attractor point. Here, j is an integer and jk n+jk is the period of the attractor for the points in the daughter µ-atom that the queryed point is close to. Because Z and Z are close to each other, _QUERY thinks that they are Z and Z and that the attractor point has n n+jk n n+k been found. _QUERY can be made "smarter" by using the RHOP algorithm described in Dewdney's article. This would make it quite a bit slower but less likely to be "fooled" the way it is now. _JULIA can also be improved, most effectively by increasing the precision of math used. It would also be nice to distinguish dusts from connected curves and fill in the latter (somehow) with black. _JULIA could be taken to the ultimate extreme by plotting Julia curves the same way the Mandelbrot Set is plotted. This would make it much slower, but would produce prettier and entirely accurate pictures. (In Mandelbrot's book Julia curves are shown this way.) The low-level math routines can probably be optimized just a little bit more (particularly the 18-bit routines.) Perhaps another intermediate resolution (such as 20 bits) can be found which is faster than the current 18-bit algorithm; then it could replace the 18-bit routines. Resource File Users of ResEdit and other resource utility programs will find the following resources in Super MANDELZOOM 1.0: BNDL 128, FREF 128, ICN# 128, rpmµ 128 -- These resources tell the Finder that the file is an application and show it what icon to put up on the screen. CODE 0 & 1 -- The program itself, assembled and linked in one segment with the MDS assembler from Apple. CURS 2 & 4 -- These cursors override the System file's standard "wristwatch" and "plus" cursors when the program is running. I made the wristwatch look like an hourglass just for fun. The "plus" cursor had to be changed because the one in Apple's System file is not totally symmetrical. CURS 1005 -- The "Select and Zoom" cursor. CURS 1000, 1001, 1002, 1003, 1004, 1006 -- These are all cursors I thought of using at various times while I was developing the program. I left them in the resource file in case I ever decided to use them again. FKEY 9 -- The SHIFT-CMD-9 function key, described under "Function Keys" above. Put this in your System file if you want to have use of it all the time. FOND 4 & 20 -- These are the font-family tables which the Mac Plus uses to find the Narrow Monaco and Times fonts. FONT 512, 521, 522, & 530 -- The Narrow Monaco font overrides the standard Monaco font while Super MANDELZOOM is running. If you use the Font/DA mover to move this font into a System file, it will renumber the font so that it no longer overrides Monaco. FONT 2560, 2570, & 2578 -- The Times font. The 20-point version has been modified; it contains lots of special characters used for the program's display. ICON 1000, 1001, 1002, 1003, 1004, 1005, 1007, 1008 -- All of these icons are used by the program. ICON 1006 -- This was an alternative "Select and Zoom" icon that I thought of using for a while. MENU 128, 129, & 130 -- The program's three menus. STR 1000, 1001, & 1002 -- Three pieces of text used in the display. I haven't bothered to put the rest of the program's text in resource format yet. Pleasing Areas of the Mandelbrot Set that I Have Found The Mandelbrot Set is full of variety, unlike most fractals. Almost any region of the Mandelbrot Set will provide beautiful pictures. To give you an idea of the kinds of things you can find, here are a few of my favorite regions: Center: -.917 +.265 i Size: .062 Options: Shading table # 4, 16-bit math, MaxCount = 500 Time: About 4 minutes (256x256 resolution) 1. This is the one which appeared on the cover of the August 1985 Scientific American. Shading table # 4 in my program was designed specifically to match that picture - I used a photocopy machine to produce a black-and-white version of it and fiddled with the shading table until I got it just right. Center: -.7455 +.1104 i Size: .0078 Options: Shading table # 5, 16-bit math, MaxCount = 500 Time: About 8 minutes (256x256 resolution) 2. This is most of the picture in figure (a) on page 18 of Dewdney's article. The spiral shaped curlicue near the top of the image will show many interesting features when enlarged (as the other figures in that article show.) Center: -.050 +.670 i Size: .016 Options: Shading table # 4, 16-bit math, MaxCount = 1000 Time: About 6 minutes (256x256 resolution) 3. This area is similar to number 2 above, but here the spirals have three arms each and look quite a bit like "galaxies." Center: +.26574 -.00320 i Size: .00012 Options: Shading table # 4, 30-bit math, MaxCount = 1000 Time: About 6 minutes (128x128 resolution) 4. This is a "miniature Mandelbrot Set", a tiny replica of the main Mandelbrot Set, and as you can see it is quite "lopsided" or distorted. By searching more closely to the cusp at 0.25 + 0.00 i, smaller and even more distorted miniature Mandelbrot Sets like this one can be found. Center: -.579 +.487 i Size: .031 Options: Shading table # 4, 16-bit math, n_max = 500 Time: About 5 minutes (256x256 resolution) 5. This is a 12-pointed "star" (filament structure) with "arms" that vary in length in an irregular pattern. At the end of each arm is a smaller star with the same irregular pattern. Center: -.02641 +.74842 i Size: .00098 Options: Shading table # 3. 30-bit math, n_max = 500 Time: About 4 1/2 minutes (128x128 resolution) 6. This is one of my favorite images (along with many others I have found which are like it) because it shows three-armed spirals, four-armed spirals, and five-armed "stars" in the same picture. (The five-armed stars are a bit hard to see; the largest is at the bottom of the picture, centered at -.02619 +.74800 i.) This image is part of the filament structure of the µ-atom which I call "M.3.4.2-5". That µ-atom has a period of 60; the larger µ-atom to which it is attached has a period of twelve, and the µ-atom to which that µ-atom is attached has a period of three. The reason the features in this picture have three, four, and five sides is because of these numbers (3, 12, and 60.) This type of relationship is universal. For example, if you check example # 1, you will notice that its filament structure has five-pointed stars and two-armed spirals; these numbers five and two are directly related to the µ-atom's period (10) and its parent's period (2). With sufficient patience you will be able to find filament structures with any desired combination of features. Note that miniature Mandelbrot Sets (such as the one at -.02600 +.74805 i in this image) appear to be at the center of a four-armed star -- but this four-armed "star" is a different kind of star from the "stars" associated with the parent µ-atom's period. This image is a good example of one for which the adjacency algorithm does no good -- it takes almost exactly four times as long to finish in 256x256 resolution as it does in 128x128 resolution. User Feedback I would enjoy hearing from you if you find other parts of the Mandelbrot Set which you consider interesting or unique. I would also like to hear from you if you have suggestions for improvements in the program, if you find bugs, and/or figure out a way to fix them. I would particularly enjoy hearing about any desk accessories which are useful with the program, such as a screen-saver which allows Super MANDELZOOM to continue running, or a D.A. that lets you paste from the clipboard directly into a MacPaint document (so I don't have to use the Scrapbook all the time.) Robert P. Munafo Barrington, Rhode Island October 26, 1986